Computer graphics applications tend to be data heavy, in that they generally require very large amounts of data to enable the graphical scenes associated therewith to be correctly rendered for viewing. This is especially true for applications involving virtual reality with moving scenes. 3D environments, where changes of viewing position may require redrawing of both the background and foreground objects displayed thereon are particularly data intensive. In general, the more accurately that the appearance of a 3D scene reflects reality, the more data is required to define it and the more effort is required to manipulate the data and render it into a displayable form.
As illustrated in FIGS. 1 and 2, networked computing comprises computers interacting via a data link. This can be generalized to a plurality of remote computer terminals, interacting with the same computer application via a network. The computers are often at a considerable distance from each other.
Where an application permits a plurality of users to view the same graphic interface, and where each terminal interface is updated with respect to interactions in real time, at least the changes to the currently viewed scene may require to be transferred to each terminal via the network. A change to an element within a dynamically changing scene such as a rotation, translation or transformation thereof generally requires the element to be redrawn. Sometimes changes may require regeneration of a whole scene, that is, the whole scene display may require redrawing.
Now the speed at which a computer application runs is a function of its complexity and the capability of the hardware. In networked computing however, particularly with data-intensive, heavy applications, the speed at which applications run, is often limited by the time required for necessary data to be transferred between computers. This data transfer time is a function of the bandwidth of the data transfer lines, and of the volume of data that requires transporting.
For networked computing in general, there is a desire to limit the quantity of data that is transported between computers, and efficient programming and data compression techniques are used to facilitate this data limiting. Some of these methods are specific to certain types of data. For example, some methods of data compression work best with text. Many graphical data compression techniques are most effective when dealing with 2D data, and only a few specific methods are suitable for 3D graphical data.
The Internet is a multiple-user, computing environment that potentially allows many users to interact with each other using the same application, enabling many players to play the same adventure game for example. To facilitate multiplayer interaction in a 3D virtual graphic environment in real-time, it is required that changes or moves made by one user, are transmitted to other users fast enough that correct sequencing is maintained, and preferentially the moves of one player appear instantaneously on the monitors of all other players. Achieving real-time updating of high-resolution 3D graphical displays at a plurality of user terminals is a challenging aim.
Apart from games and the like, virtual reality has also been applied to a variety of areas of human endeavor to simulate reality where, due to economic, safety and other considerations, it has been deemed preferable to use simulations rather than the real thing. Examples of this include prototyping objects of manufacture using computer aided design programs, anatomical simulations of the human body for pedagogic purposes in the training of doctors and surgeons, flight simulators for training aircraft pilots, and battlefield simulation for training military personnel such as tank drivers and gunners.
Now virtual reality often features changes in the appearance of virtual scene elements, perhaps as a result of rotation of objects represented, a change in viewing angle, or a change in position or movement of the object due perhaps to a user interaction. There may be a demand for fast scene regeneration, preferably in real time, and this puts a limitation on the amount of processing to affect the change. Particularly in networked computing, where the data defining an scene may require transferring between nodes on the network, there may be a requirement to limit the amount of data required to define the appearance of scene elements.
The common approach to giving an acceptable 3D appearance to a virtual scene on a 2D visual display unit (VDU), is to construct the 3D surface from elements and objects from which the scene is comprised of, namely polygonal facets. A polygonal facet is a flat element bounded by a closed loop. The boundary of the polygonal facet may be defined by the XYZ coordinates of the vertices thereof. In addition to representing a surface by polygonal facets, geometry can also be represented by polynomial and rational functions including piecewise polynomial and piecewise rational functions, and many solid-modeling environments extensively use freeform polynomial and rational curves and surfaces for defining shapes. Freeform functions can additionally be used for modeling objects whose shapes are comprised from simple geometrical elements. For example, geometric computer aided design (CAD), computer aided manufacturing (CAM) and Computer Aided Engineering (CAE) packages represent cylinders, spheres, cones and other simple geometrical shapes as rational equations, using Bezier and B-spline forms. Defining objects by rational equations is generally more compact than the multiple polygon faceted form that is typically used in virtual reality environments.
Further details concerning Bezier curves and associated methods may be obtained from Gerald Farin, Curves and Surfaces for CAGD, A Practical Guide, 4th Edition. Academic Press, N.Y., 1997, the contents of which are hereby incorporated by reference.
Higher data compression can be achieved, if, where appropriate, shapes and forms, or pieces thereof are represented as standard geometrical solid types, giving a size, position and orientation thereof in space. Thus a screen object representing, say, a tin can, may be compactly represented as being a cylinder having a certain position in space, a certain orientation and height, and a certain radius, that is in the analytical form: cylinder XPoint YPoint ZPoint Xdir Ydir Zdir R where (XPoint , YPoint , ZPoint) are the coordinates of a selected point associated with the cylinder such as the center of the base thereof, or the centroid thereof, (Xdir Ydir Zdir), define both the height of the cylinder and the orientation of its axis, and R is the radius of the cylinder. The above analytical representation is not limited to shapes that can be adequately modeled as basic primitives however. More complex shapes may often be represented as comprising a plurality of basic primitives. Thus, a bucket with a handle may be represented as an inverted truncated cone, the handle thereof being represented by an arc, perhaps a section of a circumference, for example. Such high-level representation has been considered for the compact transmission of geometry, see Shmueli and Elber [Shmueli O., and Elber G., An Architecture for Data Interaction Using Three Dimensional Environments, CS Technion Technical Report, CIS9623, Technion, December 1996], the contents of which are incorporated herein by reference. However, for virtual reality applications, such representation is generally unsuitable as the interfacing between the processor and the VDU at the client site is generally handled by dedicated graphics hardware circuitry for speed, and this hardware is specially adapted to handling polygons. Thus for non-polygonal data representations, more work is required at the client site to convert the geometry into a polygonal, displayable form.
A set of data points or function in two dimensions can be fitted with a polynomial of a suitable order. Where the required polynomial is of a particularly high order, a more practical approach than using a single approximating polynomial is to use splines. Splines are smooth piecewise polynomials that can be used to represent functions over large intervals. Because splines are smooth and easy to manipulate, they have become a standard tool for modeling arbitrary functions. The spline model is often used when the function to be modeled is only given as the solution of a functional equation.
A well-known type of spline is the NURBS, the name being an acronym of Non-Uniform Rational B-splines. Using NURBS is a popular method for representing curve and surface geometry in such diverse industries as Computer aided design (CAD), Computer aided manufacturing CAM, Computer aided engineering CAE, computer graphics, entertainment and 3-D animation, medical and geosciences.
High-level graphical representations are not highly portable between platforms. Nevertheless, Elber and Kim [Elber G., Kim M. S., Geometrical Shape recognition of Freeform Curves and Surfaces. Graphical Models and Image Processing, Vol. 59, No. 6, p.p. 417-433, November 1997] have demonstrated that higher level graphical representations may be recovered, using matching techniques, from B-splines, surfaces, curves etc. and may be transferred, between different solid modeling systems. Elber and Kim's approach uses tools from differential geometry, and carries out a process of reverse engineering to identify B-Splines or any other piecewise polynomial, and/or rational function. Having identified such a function, it then attempts to detect underlying shapes. Underlying shapes are detected by formulating necessary and sufficient conditions for a freeform curve to be a line or a circle. The approach also formulates the necessary and sufficient conditions for a freeform surface to be planar, spherical, a circular cone, a circular cylinder, a surface of revolution, a ruled surface, an extrusion surface or a sweep surface and may be extended to other shapes as well.
By way of example, suitable conditions for a rational planar curve to be circular are now given:
Let E(t) be the evolute of planar parametric curve C(t). (An evolute is the envelope of normals to a given curve, or, in other words, the locus of the centers of curvature).
E(t)=C(t)+N(t)/κ(t) where N(t) is the normal field of C(t) and κ(t) is the curvature of C(t). Then C(t) is circular, if E(t) degenerates into a single point.
It is further shown in Elber and Kim, that if C(t) is rational, then so is E(t), But then given C(t), one can evaluate E(t) as a rational form, say using B-spline representation, and examine all the control points of E(t) for similarity. If E(t) does degenerate into a single point, then C(t) is circular.
Similar approaches, also described by Elber and Kim, formulate the necessary and sufficient conditions for a freeform surface to be planar, spherical, a circular cone, a circular cylinder, a surface of revolution, a ruled surface, an extrusion surface or a sweep surface. These conditions are then used in similar robust algorithms that determine whether one of a predetermined list of shapes is present, and which may be used for the geometrical shape recognition of these basic lines and shapes. The shapes may then be used as basic primitives for analyzing the form of solid objects. Elber and Kim have thus shown the feasibility of improved transfer of geometric data between CAD platforms.
Another challenge is the conversion of low-level geometry into a high level description, particularly the conversion of low-level polygonal geometry into polynomial and rational forms. Although generally difficult, sometimes, such as when using the output from a 3D scanner, the problem is greatly simplified. The output of 3D scanners is generally an ordered set of point clouds. Instead of converting this point cloud into a mesh of polygonal data, the point cloud may be represented as a B-spline surface representing coarse information, and a pixel map holding the finer details. This approach was suggested by Krishnamurthy and Levoy [Krishnamurthy V. and Levoy M., Fitting Smooth Surfaces to Dense Polygonal Meshes, Computer Graphics Proceedings, Annual Conference Serious, Siggraph, August 1996, pp. 313-324, New Orleans, La.], the contents of which are hereby incorporated by reference. Alternatively, interpolation methods may be used on the set of unordered points or triangulations, and Farin has discussed interpolation methods of this type [Gerald Farin, Curves and Surfaces for CAGD, A practical guide, 4th Edition, Academic Press, New York, 1997], the contents of which are hereby incorporated by reference.
Finally, there have been some efforts made at the representation of 3D objects as high level polynomials and functional forms in order to achieve compact transmission of geometrical data, as discussed by Shmueli and Elber [Shmueli O. and Elber G., An Architecture for Data Interaction using three Dimensional Environments, CS Technion Technical Report, CIS9623, Technion, Haifa, Israel, December 1996], the contents of which are hereby incorporated by reference. By “functional” is meant the representation of a geometric entity by a procedural description of a basic geometrical form describing the entity followed by the parameters of the entity, thus providing the information needed for reconstruction of the entity. Shimueli and Elber describe a system for downloading and transmitting high-level polynomial descriptions to remote user sites, for display by a graphics system on a screen. The transformation is both fast and efficient, and highly detailed virtual scenes such as offices and show rooms may be transmitted in this manner using only dozens of kilobytes of data.